package com.example.project.sort.insertsort;

/**
 *  尔排序(Shell’s Sort)是插入排序的一种，是直接插入排序算法的一种更高版本的改进版本。
 * 把记录按步长gap分组，对每组记录采用直接插入排序方法进行排序；
 * 随着步长逐渐减小，所分成的组包含的记录越来越多；
 * 当步长值减小到1时，整个数据合成一组，构成一组有序记录，完成排序；
   *https://www.cnblogs.com/ksh1998/p/15658154.html
 * https://blog.csdn.net/YelloJesse/article/details/90724105
 * 对于{1,2,3,4,5,6,7,8,9,10}
 * 选取d为5，那么我们就对{1,6}，{2,7}，{3,8}，{4,9},10
 * 待排序的位置默认每个组看起来都是从gap以后开始的。
 * 第1组待排的是a5,第2组待排的是a6,第3组待排的h是a7,第四组待排的是a8 几个组共同点是都是从gap往后开始的
 *https://www.bilibili.com/video/BV1BK4y1478X?spm_id_from=333.337.search-card.all.click
 *
 */
public class ShellSort {

    //稳定性：不稳定
    public static void shellSort(int[] arr) {
        // 空数组 或 只有一个元素的数组，则什么都不做。
        if(arr == null || arr.length == 1){
            return;
        }
        int k = arr.length/2;
        while (k!=0){
            for(int i = k;i<arr.length;i++){ //待排序的位置从step开始,但是排的是里面有间距的分割符号。知道最候为1了，才代表最后排一次了，移动少了
                
                int x = arr[i];//空出i的位置也可以出说是哨兵
                int j;
                //这里同时排几个分组的队列，直接排序哪里以前的1变为step
                for(j = i-k;j>=0 && arr[j]> x ;j-=k){
                    arr[j+k]=arr[j];//满足条件的j往后移动，移动之后，默认j会往前面走一位呢,会再空位的前面以为
                }
                arr[j+k]=x;//所以这里是j+k,是空白的位置呢
            }
            k = k/2;
        }
    }

    public static void main(String[] args) {

    }

}
